#include "../linear/linear.h"

struct Node {
	int item;
	struct Node* left;
	struct Node* right;
	int n;
};

struct Node* put(struct Node* node, int item) {
	if (node == NULL) {
		node = (struct Node *) malloc(sizeof(struct Node));
		node->item = item;
		node->n = 1;
		node->left = NULL;
		node->right = NULL;
		return node;
	}
	if (item > node->item) 
		node->right = put(node->right, item);
	else if (item < node->item)
		node->left = put(node->left, item);
	return node;
}

struct Node* get(struct Node* node, int item) {
	if (node == NULL)
		return NULL;
	if (item == node->item)
		return node;
	if (item > node->item)
		return get(node->right, item);
	if (item < node->item)
		return get(node->left, item);
}

void recursiveTraversal(struct Node* root) {
	if (root == NULL) 
		return;
	printf("%d ", root->item);
	recursiveTraversal(root->left);
	recursiveTraversal(root->right);
}

void cycleTraversal(struct Node *root) {
	struct Stack *stack;
	struct Node *node = root;

	stack = (struct Stack *) malloc(sizeof(struct Stack));
	stack->first = NULL;
	while (node != NULL || !stack_is_empty(stack)) {
		if (node != NULL) {
			push(stack, node->item);
			printf("%d ", node->item);
			node = node->left;
		} else {
			node = get(root, pop(stack));
			node = node->right;
		}
	}
	free((void *) stack);
}

void cyclePostTraversal(struct Node *root) {
	struct Node *node = root;
	struct Stack *stack;
	int t;

	stack = (struct Stack *) malloc(sizeof(struct Stack));
	stack->first = NULL;

	while (node != NULL || !stack_is_empty(stack)) {
		if (node != NULL) {
			push(stack, node->item);
			node = node->left;
		} else {
			node = get(root, pop(stack));
			if (node->right != NULL && t != node->right->item) {
				push(stack, node->item);
				node = node->right;
				push(stack, node->item);
				node = node->left;
			} else {
				t = node->item;
				printf("%d ", t);
				node = NULL;
			}
		}
	}
}

void levelTraversal(struct Node* root) {
	struct Queue* queue;
	struct Node* node = root;

	queue = (struct Queue *) malloc(sizeof(struct Queue));
	queue->first = NULL;
	queue->last = NULL;
	enqueue(queue, node->item);
	while (!queue_is_empty(queue)) {
		int val = dequeue(queue);
		printf("%d ", val);
		node = get(root, val);
		if (node->left != NULL)
			enqueue(queue, node->left->item);
		if (node->right != NULL)
			enqueue(queue, node->right->item);
	}
	free((void *) queue);	
}

void main() {
	struct Node* root = put(root, 40);
	put(root, 20);
	put(root, 30);
	put(root, 10);
	put(root, 60);
	put(root, 50);
	put(root, 70);
	recursiveTraversal(root);
	printf("\n");
	levelTraversal(root);
	printf("\n");
	cycleTraversal(root);
	printf("\n");
	cyclePostTraversal(root);
	printf("\n");
}
